home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsi / polyscan / polyclip.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-26  |  4.6 KB  |  145 lines
  1. /*
  2.  * Generic Convex Polygon Scan Conversion and Clipping
  3.  * by Paul Heckbert
  4.  * from "Graphics Gems", Academic Press, 1990
  5.  */
  6.  
  7. /*
  8.  * poly_clip.c: homogeneous 3-D convex polygon clipper
  9.  *
  10.  * Paul Heckbert    1985, Dec 1989
  11.  */
  12.  
  13. #include <stdio.h>
  14. #include "poly.h"
  15.  
  16. #define SWAP(a, b, temp)    {temp = a; a = b; b = temp;}
  17. #define COORD(vert, i) ((double *)(vert))[i]
  18.  
  19. #define CLIP_AND_SWAP(elem, sign, k, p, q, r) { \
  20.     poly_clip_to_halfspace(p, q, &v->elem-(double *)v, sign, sign*k); \
  21.     if (q->n==0) {p1->n = 0; return POLY_CLIP_OUT;} \
  22.     SWAP(p, q, r); \
  23. }
  24.  
  25. /*
  26.  * poly_clip_to_box: Clip the convex polygon p1 to the screen space box
  27.  * using the homogeneous screen coordinates (sx, sy, sz, sw) of each vertex,
  28.  * testing if v->sx/v->sw > box->x0 and v->sx/v->sw < box->x1,
  29.  * and similar tests for y and z, for each vertex v of the polygon.
  30.  * If polygon is entirely inside box, then POLY_CLIP_IN is returned.
  31.  * If polygon is entirely outside box, then POLY_CLIP_OUT is returned.
  32.  * Otherwise, if the polygon is cut by the box, p1 is modified and
  33.  * POLY_CLIP_PARTIAL is returned.
  34.  *
  35.  * Given an n-gon as input, clipping against 6 planes could generate an
  36.  * (n+6)gon, so POLY_NMAX in poly.h must be big enough to allow that.
  37.  */
  38.  
  39. int poly_clip_to_box(p1, box)
  40. register Poly *p1;
  41. register Poly_box *box;
  42. {
  43.     int x0out = 0, x1out = 0, y0out = 0, y1out = 0, z0out = 0, z1out = 0;
  44.     register int i;
  45.     register Poly_vert *v;
  46.     Poly p2, *p, *q, *r;
  47.  
  48.     if (p1->n+6>POLY_NMAX) {
  49.     fprintf(stderr, "poly_clip_to_box: too many vertices: %d (max=%d-6)\n",
  50.         p1->n, POLY_NMAX);
  51.     exit(1);
  52.     }
  53.     if (sizeof(Poly_vert)/sizeof(double) > 32) {
  54.     fprintf(stderr, "Poly_vert structure too big; must be <=32 doubles\n");
  55.     exit(1);
  56.     }
  57.  
  58.     /* count vertices "outside" with respect to each of the six planes */
  59.     for (v=p1->vert, i=p1->n; i>0; i--, v++) {
  60.     if (v->sx < box->x0*v->sw) x0out++;    /* out on left */
  61.     if (v->sx > box->x1*v->sw) x1out++;    /* out on right */
  62.     if (v->sy < box->y0*v->sw) y0out++;    /* out on top */
  63.     if (v->sy > box->y1*v->sw) y1out++;    /* out on bottom */
  64.     if (v->sz < box->z0*v->sw) z0out++;    /* out on near */
  65.     if (v->sz > box->z1*v->sw) z1out++;    /* out on far */
  66.     }
  67.  
  68.     /* check if all vertices inside */
  69.     if (x0out+x1out+y0out+y1out+z0out+z1out == 0) return POLY_CLIP_IN;
  70.  
  71.     /* check if all vertices are "outside" any of the six planes */
  72.     if (x0out==p1->n || x1out==p1->n || y0out==p1->n ||
  73.     y1out==p1->n || z0out==p1->n || z1out==p1->n) {
  74.         p1->n = 0;
  75.         return POLY_CLIP_OUT;
  76.     }
  77.  
  78.     /*
  79.      * now clip against each of the planes that might cut the polygon,
  80.      * at each step toggling between polygons p1 and p2
  81.      */
  82.     p = p1;
  83.     q = &p2;
  84.     if (x0out) CLIP_AND_SWAP(sx, -1., box->x0, p, q, r);
  85.     if (x1out) CLIP_AND_SWAP(sx,  1., box->x1, p, q, r);
  86.     if (y0out) CLIP_AND_SWAP(sy, -1., box->y0, p, q, r);
  87.     if (y1out) CLIP_AND_SWAP(sy,  1., box->y1, p, q, r);
  88.     if (z0out) CLIP_AND_SWAP(sz, -1., box->z0, p, q, r);
  89.     if (z1out) CLIP_AND_SWAP(sz,  1., box->z1, p, q, r);
  90.  
  91.     /* if result ended up in p2 then copy it to p1 */
  92.     if (p==&p2)
  93.     bcopy(&p2, p1, sizeof(Poly)-(POLY_NMAX-p2.n)*sizeof(Poly_vert));
  94.     return POLY_CLIP_PARTIAL;
  95. }
  96.  
  97. /*
  98.  * poly_clip_to_halfspace: clip convex polygon p against a plane,
  99.  * copying the portion satisfying sign*s[index] < k*sw into q,
  100.  * where s is a Poly_vert* cast as a double*.
  101.  * index is an index into the array of doubles at each vertex, such that
  102.  * s[index] is sx, sy, or sz (screen space x, y, or z).
  103.  * Thus, to clip against xmin, use
  104.  *    poly_clip_to_halfspace(p, q, XINDEX, -1., -xmin);
  105.  * and to clip against xmax, use
  106.  *    poly_clip_to_halfspace(p, q, XINDEX,  1.,  xmax);
  107.  */
  108.  
  109. void poly_clip_to_halfspace(p, q, index, sign, k)
  110. Poly *p, *q;
  111. register int index;
  112. double sign, k;
  113. {
  114.     register unsigned long m;
  115.     register double *up, *vp, *wp;
  116.     register Poly_vert *v;
  117.     int i;
  118.     Poly_vert *u;
  119.     double t, tu, tv;
  120.  
  121.     q->n = 0;
  122.     q->mask = p->mask;
  123.  
  124.     /* start with u=vert[n-1], v=vert[0] */
  125.     u = &p->vert[p->n-1];
  126.     tu = sign*COORD(u, index) - u->sw*k;
  127.     for (v= &p->vert[0], i=p->n; i>0; i--, u=v, tu=tv, v++) {
  128.     /* on old polygon (p), u is previous vertex, v is current vertex */
  129.     /* tv is negative if vertex v is in */
  130.     tv = sign*COORD(v, index) - v->sw*k;
  131.     if (tu<=0. ^ tv<=0.) {
  132.         /* edge crosses plane; add intersection point to q */
  133.         t = tu/(tu-tv);
  134.         up = (double *)u;
  135.         vp = (double *)v;
  136.         wp = (double *)&q->vert[q->n];
  137.         for (m=p->mask; m!=0; m>>=1, up++, vp++, wp++)
  138.         if (m&1) *wp = *up+t*(*vp-*up);
  139.         q->n++;
  140.     }
  141.     if (tv<=0.)        /* vertex v is in, copy it to q */
  142.         q->vert[q->n++] = *v;
  143.     }
  144. }
  145.